#include <stdio.h>

/*
 * 二叉树查找
 */

typedef int keytype;

	typedef struct {
		keytype Key;
	}elemtype;

// 非递归算法

btree *search(btree *b,int x)
{
/*在二叉树b中查找x的过程*/
if(b=NULL) 
  return(NULL);
	
 else{
if(b->data==x) 
  return(b);
if(x<b->data) 
  return(search(b->left));
 else 
   return(search(b->right));
} 
}


// 递归算法

bsnodetype *Search_r(bsnodetype *bt,keytype Key)
{
/*在二叉树bt中查找元素为Key的元素*/
bsnodetype *p;
if(bt==NULL) 
  return(bt);

p=bt;
while(p->Key!=Key){
if(Key<p->Key) 
  p=p->Lchild;
 else 
   p=p->Rchild;
if(p==NULL)
  break;
}
return(p);
}


// 生成二叉树

// 向一个二叉树b中插入一个结点s的函数如下：
void insert(b,s)
{
btree *b,*s;
		
if(b==NULL) 
  b=s;
 else if(s->data==b->data) 
   return();
 else if(s->data<b->data)
   insert(b->left,s);
 else if(s->data>b->data)
   insert(b->right,s);
}

// 创建二叉树
void create(btree *b)
{
int x;
btree 8s;
b==NULL;
	
do{
scanf("%d",&x);
s=(bnode *)malloc(sizeof(bnode));
s->data=x;
s->left=NULL;
s->right=NULL;
insert(b,s); 
}while(x!=-1);
}

// 从二叉树中删除一个结点
bsnodetype *Delete(bsnodetype *bt,keytype Key)/*在bt为根结点的二叉树中删除值为Key的结点*/
{	
bsnodetype *p,*q;
if(bt->Key==Key){
/*bt的左右子树均为空*/
if(bt->Lchild==NULL&&bt->Rchild==NULL){
free(bt); /*删除叶结点*/
return(NULL);
}else if(bt->Lchild==NULL){ /*bt的左子树为空*/
p=bt->Rchild;
free(bt);
return(p);
}else if(bt->Rchild==NULL){/*bt的右子树为空*/
p=bt->Lchild;
free(bt);
return(p); 
}else{
p=q=bt->Rchild;
while(p->Lchild!=NULL)
  p=p->Lchild;
p->Lchild=bt->Lchild;
free(bt);
return(q);
}
}
	
/*在bt->Lchild为根结点的二叉树中删除值为Key的结点*/
if(bt->Key>Key&&bt->Lchild!=NULL)
  bt->Lchild=Delete(bt->Lchild,Key);
	
/*在bt->Rchild为根结点的二叉树中删除值为Key的结点*/
if(bt->Key<Key&&bt->Rchild!=NULL)
  bt->Rchild=Delete(bt->Rchild,Key);
	
return(bt);
}

int main()
{

}
